package com.buddy.learn.algorithm.simple;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author Buddy
 * @date 2021/4/22
 */
public class CityConnections {

    public static void main(String[] args) {
        List<Integer> costList = new ArrayList<>();
        //Input: N = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
        Map<Integer, Integer> cache = new HashMap<>(4);
        for (int i = 1; i <= 3; i++) {
            cache.put(i, i);
        }


        CityConnection cs11 = new CityConnection(1, 2, 5);
        CityConnection cs12 = new CityConnection(1, 3, 6);
        CityConnection cs23 = new CityConnection(2, 3, 1);

        List<CityConnection> list = new ArrayList<>();
        list.add(cs11);
        list.add(cs12);
        list.add(cs23);

        List<CityConnection> sortedList = list.stream().sorted(Comparator.comparingInt(o -> o.cost)).collect(Collectors.toList());

        CityConnection first = sortedList.get(0);
        cache.remove(first.city_1);
        cache.remove(first.city_2);
        costList.add(first.cost);

        for (int i = 1; i < sortedList.size(); i++) {
            CityConnection curr = sortedList.get(i);
            int city1 = curr.city_1;
            int city2 = curr.city_2;
            boolean flag = false;
            if (cache.containsKey(city1)){
                cache.remove(city1);
                flag = true;
            }
            if (cache.containsKey(city2)){
                cache.remove(city2);
                flag = true;
            }

            if (flag){
                costList.add(curr.cost);
            }
        }
       System.out.println(costList.stream().mapToInt(cost -> cost).sum());
    }


}

class CityConnection {
    int city_1;
    int city_2;
    int cost;

    public CityConnection(int city_1, int city_2, int cost) {
        this.city_1 = city_1;
        this.city_2 = city_2;
        this.cost = cost;
    }

}